/* Gionata Massi <gionata.massi@gmail.com>
 * Febbraio 2007
 *
 * File: localsearch.cpp
 *
 * Questo file fa parte di 'aga'
 */

/*!
  \file		localsearch.cpp
  \brief	Solutore MOSP e MOSPk mediante algoritmo genetico.
  \author	Gionata Massi
  \version	2009-07-23
  \date		2009-03-23

  Ricerca locale, con vicinato 2-Opt e Reciprocal Exchange.
 */

#include "aga.h"
#include <float.h>
#if defined (DLL_EXPORT)
#	define NDEBUG
#endif
// #include <assert.h>

/* La sequenza di partenza */
static Individual neigh;
static Individual bestNeigh;

static int nGenes = 0;

void localsearch_initializer(GeneticData * data)
{
	nGenes = data->NumGenes;

	neigh.Sequence = (Gene *) calloc(nGenes, sizeof(Gene));
	bestNeigh.Sequence = (Gene *) calloc(nGenes, sizeof(Gene));
	data->stat.local_searches = 0;
}

void localsearch_finalizer()
{
	free(neigh.Sequence);
	free(bestNeigh.Sequence);
}

int ls_2opt_ind(GeneticData * data, int ind_idx)
{

	double norm_w[parameters];
	double ub[parameters], lb[parameters];

	if (data->People[ind_idx].LS_performed[LS_2Opt_INDEX])
		return -1;

	for (int p = 0; p < parameters; p++) {
		ub[p] = data->UB[p];
		lb[p] = data->LB[p];
		norm_w[p] = data->k[p];
	}

	int m = nGenes;
	Gene *& s = data->People[ind_idx].Sequence;
	Ranking & current_score = data->People[ind_idx].Score;
	Gene *& n = neigh.Sequence;
	Ranking & neigh_score = neigh.Score;
	Gene * & b = bestNeigh.Sequence;
	Ranking & best_score = bestNeigh.Score;

	// Valuta gli indicatori di performance e la fitness
	if (!data->People[ind_idx].performance_indicators_evaluated)
		evaluate_performance_indicators(data, s, &current_score);
	data->People[ind_idx].performance_indicators_evaluated = 1;
	fitness_function(data, &current_score, norm_w, lb, ub);
	best_score = current_score;

	int depth = -1;
	bool improvement;
	data->stat.local_searches++;

#ifdef VERBOSE_DEBUG
	fprintf(stderr,
	        "LS: %6ld\tPhase: %d\tIndividual: %d\tInitial_MOS: %d\n",
	        data->stat.local_searches, data->CurrentPhase, ind_idx,
	        current_score.measure[MOS]);
	fflush(NULL);
#endif
	do {
		improvement = false;
		depth++;

#ifdef VERBOSE_DEBUG
		fprintf(stderr,
		        "\tDepth: %4d\tMOS: %3d\tfitness: %9.7f\tBest MOS: %3d\tPhase: %2d\n",
		        depth, current_score.measure[MOS], current_score.score,
		        data->BestMosInd.Score.measure[MOS],
		        data->CurrentPhase);
		fflush(NULL);
#endif

		for (int r1 = 0;
		     r1 < m - 1 && (data->LocSearchSteepDesc || !improvement);
		     r1++) {
			// 2. 2-opt
			int limit =
			    (m <
			     r1 + data->LocSearchNeighWidth) ? m : r1 +
			    data->LocSearchNeighWidth;
			for (int r2 = r1 + 2;
			     r2 < limit && (data->LocSearchSteepDesc
			                    || !improvement); r2++) {
				int i = 0;
				// Copia da 0 fino a r1
				for (int k = 0; k <= r1; k++)
					n[i++] = s[k];
				// Copia sequenza inversa r2..r1+1
				for (int k = r2; k > r1; k--)
					n[i++] = s[k];
				// Copia da r2 + 1 a m
				for (int k = r2 + 1; k < m; k++)
					n[i++] = s[k];

				evaluate_performance_indicators(data, n,
				                                &neigh_score);
				if (neigh_score.measure[TOTAL_COST] <
				    data->TheBestOne.Score.measure[TOTAL_COST]) {
					// Aggiorna la miglior soluzione trovata
					data->TheBestOne.Score = neigh_score;
					for (int k = 0; k < data->NumGenes; k++)
						data->TheBestOne.Sequence[k] =
						    n[k];
					data->stat.last_best_generation[TOTAL_COST] =
					    data->CurrentGeneration;
					data->stat.ls_found_opt = 1;
				}
				fitness_function(data, &neigh_score, norm_w, lb,
				                 ub);
				if (neigh_score.score < best_score.score) {
					for (int k = 0; k < m; k++)
						b[k] = n[k];
					best_score = neigh_score;
					improvement = true;
				}
			}
			// 1. rotazione
			if (data->LocSearchSteepDesc || !improvement) {
				int t = r1 + 1;
				for (int k = 0; k < m; k++, t = ((t + 1) % m))
					n[k] = s[t];
				evaluate_performance_indicators(data, n,
				                                &neigh_score);
				if (neigh_score.measure[TOTAL_COST] <
				    data->TheBestOne.Score.measure[TOTAL_COST]) {
					data->TheBestOne.Score = neigh_score;
					for (int k = 0; k < data->NumGenes; k++)
						data->TheBestOne.Sequence[k] =
						    n[k];
					data->stat.last_best_generation[TOTAL_COST] =
					    data->CurrentGeneration;
					data->stat.ls_found_opt = 1;
				}
				fitness_function(data, &neigh_score, norm_w, lb,
				                 ub);
				if (neigh_score.score < best_score.score) {
					for (int i = 0; i < m; i++)
						b[i] = n[i];
					best_score = neigh_score;
					improvement = true;
				}
			}
		}
		if (improvement) {
			// Aggiorna i bound
			for (int p = 0; p < parameters; p++) {
				if (best_score.measure[p] < lb[p])
					lb[p] = best_score.measure[p];
				if (best_score.measure[p] > ub[p])
					ub[p] = best_score.measure[p];
			}
			// Aggiorna i pesi normalizzati
			int phase =
			    (data->CurrentPhase >
			     -1) ? data->CurrentPhase : PHASES;
			update_k(norm_w, data->Weight[phase], lb, ub);
			// Aggiorna il solo valore della fitness
			fitness_function(data, &best_score, norm_w, lb, ub);
			// Aggiorna la soluzione corrente
			for (int i = 0; i < m; i++)
				s[i] = bestNeigh.Sequence[i];
			current_score = best_score;
		}
	} while (improvement && ((data->LocSearchDepth <= 0) || (depth < data->LocSearchDepth)) );

	data->People[ind_idx].performance_indicators_evaluated = 1;
	data->People[ind_idx].LS_performed[LS_2Opt_INDEX] = 1;
#ifdef VERBOSE_DEBUG
	fprintf(stderr, "LS %6ld complete.\n\n", data->stat.local_searches);
	fflush(NULL);
#endif
	return depth;
}
